package leetcode.Leetcode76;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

class Solution {

    //创建HashMap统计s和t中字符个数
    Map<Character, Integer> sMap = new HashMap<>();
    Map<Character, Integer> tMap = new HashMap<>();

    public String minWindow(String s, String t) {
        //只记录t中字符的个数
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            Character tCharacter = t.charAt(i);
            tMap.put(tCharacter,tMap.getOrDefault(tCharacter,0)+1);
        }

        int sLen = s.length();
        //双指针，一个往前先找，一个收缩滑动窗口
        int i = 0,j=0;
        int ansL = -1, ansR = -1;
        int ansLen=Integer.MAX_VALUE;
        while (i < sLen) {
            Character sCharacter=s.charAt(i);
            sMap.put(sCharacter, sMap.getOrDefault(sCharacter, 0) + 1);
            //每次增加了，检查一下是否覆盖
            if (check()) {
                //若为true，再收缩
                while (check()&&j<=i) {//一直检查，一直收缩
                    Character jCharacter = s.charAt(j);
                    sMap.put(jCharacter,sMap.get(jCharacter) - 1);
                    j++;
                }
                int len = i - j + 1;
                if (len < ansLen) {
                    ansLen = len;//更新最小len
                    ansL = j-1;
                    ansR = i;
                }
                //更新i,j
                //不需要更新，因为可以重复使用当前位置的元素个数。
            }
            i++;
        }
        return ansL==-1?"":s.substring(ansL,ansR+1);
    }

    public Boolean check() {
        //遍历tMap，判断是否都够用
        Iterator iterator=tMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            Character c = (Character) entry.getKey();
            Integer num = (Integer) entry.getValue();
            if (sMap.getOrDefault(c,0)<num) {//字母数量不够，返回false
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.minWindow("cabwefgewcwaefgcf", "cae");
    }
}